package practice.sort.compare;

import practice.sort.Sort;

import java.util.Random;

/**
 * @Description:
 * @Author Ammar
 * @Create 2023/8/10 09:30
 */
public class QuickSort extends Sort {
    @Override
    public void sort() {
        sort(0, nums.length - 1);
    }

    public void sort(int left, int right) {
        if (left >= right) return;
        int pivotIndex = pivotPosition(left, right);
        sort(left, pivotIndex);
        sort(pivotIndex + 1, right);
    }

    public int pivotPosition(int left, int right) {
        Random random = new Random();
        int pivotIndex = left + random.nextInt(right - left);
        int pivot = nums[pivotIndex];
        swap(pivotIndex, right);
        int storeIndex = left;
        for (int i = left; i < right; i++) {
            if (nums[i] < pivot) {
                swap(storeIndex, i);
                storeIndex++;
            }
        }
        swap(storeIndex, right);
        return storeIndex;
    }
}
